package main

func countSubstrings(s string) int {
	dp := make([][]bool, len(s))
	for i := range s {
		dp[i] = make([]bool, len(s))
	}
	cnt := 0
	for i := len(s) - 1; i >= 0; i-- {
		for j := range s {
			if i >= j {
				dp[i][j] = true
				if i == j {
					cnt++
				}
			} else {
				dp[i][j] = dp[i+1][j-1] && s[i] == s[j]
				if dp[i][j] {
					cnt++
				}
			}
		}
	}
	return cnt
}